package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/14 10:10
 *
 两个链表的第一个公共点:哈希表
 快慢指针:
 */

import java.util.HashSet;
import java.util.Set;

public class Main23 {
    class ListNode{
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    //快慢指针:O(n+m)都走m+n的长度，有交点因为走的长度一样就会相等，没交点都会走到null
    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        ListNode p1=pHead1,p2=pHead2;
        while(p1!=p2){
            p1=p1==null?pHead2:p1.next;
            p2=p2==null?pHead1:p2.next;
        }
        return p1;
    }
    //哈希表
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Set<ListNode>set=new HashSet<>();
        ListNode p=pHead1;
        while(p!=null){
            set.add(p);
            p=p.next;
        }
        p=pHead2;
        while(p!=null){
            if(set.contains(p))return p;
            p=p.next;
        }
        return null;
    }
    public static void main(String[] args) {

    }
}
